Codeforces Round #623 Div2 A~D题解

本场链接:Codeforces Round #623
A. Dead Pixel
题目大意:有一个$a\star b$大小的电视机,坐标从$0$开始.上面有一个像素点坏了,问不包括这个坏掉的像素点的矩形最大的面积是多少.
数据范围:
$1 \leq a,b \leq 10^4$
$a + b > 2$

这题还是比较显然的,去掉这个坏掉的像素点之后,最大的矩形就四种情况,分别求一个最大值就行了.
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n,m,x,y;scanf("%d%d%d%d",&n,&m,&x,&y);
		int res = 0;
		res = max(res,max(n * y,n * (m - y - 1)));
		res = max(res,max(m * x,m * (n - x - 1)));
		printf("%d\n",res);
    }
    return 0;
}

B. Homecoming
原题大意:一个人一开始在$1$号位置,一条路上一共有$n$个车站,用一个字符串$s$来表示整条路上的车站分布情况.车站一共有两种,一种是A,花费为$a$,另外一种是B,花费为$b$.车站的行驶规则是这样的:假如有一段$i~j$全是A或全是B,那么就可以从这段起点一直走到这一段的末尾的下一个位置(下一个位置可以是不同的),并支付相应的花费.现在已知$a$和$b$两种票价以及整条路径上的路线安排情况,以及手上有多少钱.问至少要走几步,才能使之后一直到$n$位置都可以只坐车到达.要求不能欠钱,也不必把钱花完.最终输出至少有几步即可.
数据范围:
$1 \leq a,b,p \leq 10^5$
$2 \leq |s| \leq 10^5$

这题的题面有点长,不过理解了之后思路还是比较明确的,只要从后往前模拟就可以了.注意模拟的退出点是:手上钱不够购买一段连续区间的车票钱,或者是已经到头了.以及要记录一个当前这一段相同区间的左端点的答案,如果退出循环之后,手上的钱是足够购买这一段区间的票钱的,那么说明应该选择这一段的右端点,如果不够,应该选这一段的左端点.细节问题稍微有点说不清楚,建议自行模拟一下这个题的过程.

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
char s[N];
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int T;cin >> T;
	while(T--)
	{
		int a,b,p;cin >> a >> b >> p;
		cin >> s + 1;
		int n = strlen(s + 1);
		int r = n - 1;
		int l = r,res = 0;
		while(l >= 0)
		{
			while(l >= 0 && s[l] == s[r])	--l;
			res = l + 1;
			if(l == 0)	break;
			if(s[r] == 'A')
			{
				if(p >= a)	p -= a;
				else break;
			}
			else if(s[r] == 'B')
			{
				if(p >= b)	p -= b;
				else break;
			}
				
			r = l;
		}
		if(p < ((s[r] == 'A') ? a : b))	cout << r + 1 << endl;
		else cout << res << endl;
	}
    return 0;
}

C. Restoring Permutation
题目大意:给定一个长度为$n$的序列$b$,找到一个字典序最小的排列$a$,长度为$2n$,并满足$b_i = min(a_{2i},a_{2i-1})$,若不存在这样的排列$c$,则输出$-1$,否则输出$c$
注意$c$是一个排列,不是单纯的序列
数据范围:
$1 \leq n \leq 100$

这题的数据范围一看这么小,肯定可以乱搞搞就过去了.
思考一下这个题具体是在问什么:找到一个排列$c$,要使这个排列满足一个性质,如果有多个,就得是最小的.

显然,对于一个数字排列来说,只要数字越小字典序也就越小,首先肯定是能选小的就选小的.其次很容易想到这个题应该是一步一步,从后往前依次把$b$里的元素放进去,再按$b$的大小构造的,每次要往$c$里造两个元素放进去,每两个都要满足之前的性质.不难想到说放完了一个$b$里的元素之后,插入一个还没有用过的比当前元素要大的数接着放进去.因为要取最小值,,如果后一个$b$里的元素被影响了(后面的这个数更大,导致之前插入给之前那个元素补更大的值在这里变成了一个较小值),说明无解.因为如果一个更大的数放在这里,这个较小的数之后不管怎样放,必然会产生矛盾,而且$c$作为一个排列不能是缺少一些数的,所以无解.
要用没有用过的数的原因是最后的$c$得是一个排列.最后如果还有没有用完的数,就把剩余的还没加进$c$的数从小到大依次放进去就好了.
至于这个查找的过程,可以直接循环遍历一下,最多也就$200$个数,随便写写就完事了.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		set<int> st;
		int n;scanf("%d",&n);
		vector<int> b(n + 17,0);
		if(n == 1)
		{
			scanf("%d",&b[0]);
			if(b[0] != 1)	puts("-1");
			else puts("1 2");
			continue;
		}
		for(int i = 1;i <= n;++i)	scanf("%d",&b[i]);
		for(int i = 1;i <= 2 * n;++i)	st.insert(i);
		for(int i = 1;i <= n;++i)	st.erase(b[i]);
		vector<int> a;a.push_back(0x3f3f3f3f);
		a.push_back(b[1]);
		for(int i = b[1];i <= 2 * n;++i)	
			if(st.count(i))
			{
				a.push_back(i);
				st.erase(i);
				break;
			}
		for(int i = 2;i <= n;++i)
		{
			a.push_back(b[i]);
			for(int j = b[i] + 1;j <= 2 * n;++j)
				if(st.count(j))
				{
					st.erase(j);
					a.push_back(j);
					break;
				}
		}
		for(int i = 1;i <= 2 * n;++i)
		{
			if(st.count(i))
				a.push_back(i);
		}
		//check
		int ok = 1;
		// for(auto& v : a)	cout << v << " ";cout << endl;
		for(int i = 1;i <= n;++i)
		{
			if(b[i] != min(a[2 * i],a[2 * i - 1]))
			{
				ok = 0;
				break;
			}
		}
		if(!ok)	puts("-1");
		else
		{
			for(int i = 1;i <= 2 * n;++i)
				printf("%d ",a[i]);
			puts("");
		}
    }
    return 0;
}

D. Recommendations
题目大意:有$n$个元素,每个元素有两种属性,一是$a_i$,另外一个是$t_i$,表示如果要让$a_i$加一,需要$t_i$的代价.现要使所有的$a_i$都不同,问最少需要多少代价.

数据范围:
$1 \leq n \leq 2\star 10^5$
爆$int$

这个题的关键在于,a_是动态变化的,如果我把一个$a_i$加一,那么其他的$a_i$的数量可能因此增加.这是一个动态的数量变化,与动态的变化的结构有很多,在这里比较容易依靠直觉想到的是堆或者用并查集维护.两种方法都可以做,这里讲一下并查集怎么做.
首先要知道并查集到底在维护什么,我们可以发现,如果对于某一个值来说,他增加了一次,那么之后所有其他值就不能采用他这个值了,就应该是这个值$+1$.所以可以维护每一个值$x$最终需要是多少.对于第一个遇到的,就是$x$,之后把$x$的祖先连接到$x+1$.动态的维护$x$最终要是多少即可.
简略说一下整个算法流程:首先贪心的按$t_i$倒序排列,因为较早出来的值其$a_i$修改的次数也越少,这样可以贪心的使整个代价较小.其次遍历每一个元素,查他的祖先,即最终需要是多少,计算一个差值,求出这个差值和$t_i$的乘积,得到应该需要增加几次,以及要多少的代价,并累加到答案里.
最后还有一个问题,因为$a_i$的值高达$10^9$,因此这里可以采用$map$来做并查集,可以避免值域的问题(也就是避免写离散化,而且离散化貌似也不能处理增加的处理).
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 2e5+7;
map<int,int> fa;
struct Node
{
	int a,b;
	const bool operator<(const Node& v) const
	{
		if(b != v.b)	return b > v.b;
		return a < v.a;
	}
}a[N];
int find(int x)
{
	if(fa[x] == 0)	return x;
	return fa[x] = find(fa[x]);
}
signed main()
{
	int n;scanf("%lld",&n);
	for(int i = 1;i <= n;++i)	scanf("%lld",&a[i].a);
	for(int i = 1;i <= n;++i)	scanf("%lld",&a[i].b);
	sort(a + 1,a + n + 1);
	ll res = 0;
	for(int i = 1;i <= n;++i)
	{
		int x = find(a[i].a);
		res += (x - a[i].a) * a[i].b;
		int nxt = find(x + 1);
		fa[x] = nxt;
	}
	printf("%lld",res);
    return 0;
}